package com.cat.dynamicPlanning;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-substring-partition-of-equal-character-frequency/
 * @create 2025/9/5 22:22
 * @since JDK17
 */

public class Solution83 {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            HashMap<Character, Integer> map = new HashMap<>();
            int max = 0;
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j > 0; j--) {
                map.merge(s.charAt(j - 1), 1, Integer::sum);
                max = Math.max(max, map.get(s.charAt(j - 1)));
                if (dp[j - 1] != Integer.MAX_VALUE && max * map.size() == (i - j + 1)) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n];
    }
}
